package zijie;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class RightSideView_199_18 {

    public List<Integer> rightSideView(TreeNode root) {
     List<Integer> res = new ArrayList<>();
     if(root == null){
         return res;
     }
     Queue<TreeNode> queue = new LinkedList<>();
     queue.offer(root);

     while (!queue.isEmpty()){
         int size = queue.size();
         for (int i = 0; i < size; i++) {
             TreeNode node  = queue.poll();
             if(node.left != null){
                 queue.add(node.left);
             }
             if(node.right != null){
                 queue.add(node.right);
             }
             if(i == size - 1){
                 res.add(node.val);
             }
         }
     }
     return res;

  }

    public List<Integer> rightSideView2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if(poll.left != null){
                    queue.add(poll.left);
                }
                if(poll.right != null){
                    queue.add(poll.right);
                }
                if(i == size - 1){
                    res.add(poll.val);
                }
            }
        }
        return res;
    }

      public static class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }

    public static void main(String[] args) {
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(2);
            root.right = new TreeNode(3);
            root.left.right = new TreeNode(5);
            root.right.right = new TreeNode(4);
        RightSideView_199_18 rightSideView_199_18 =  new RightSideView_199_18();
        rightSideView_199_18.rightSideView(root);
    }
}
